package 牛客题霸;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

/**
 * 给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。
 */
public class 有重复项数字的全排列 {

    ArrayList<ArrayList<Integer>> res;

    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        Arrays.sort(num);
        res = new ArrayList<>();
        HashSet<Integer> set = new HashSet<>();
        dfs(num, set, new ArrayList<Integer>());
        return res;
    }

    public void dfs(int[] num, HashSet<Integer> set, ArrayList<Integer> path){
        if(path.size() == num.length){
            // 枚举了所有数后，将该结果保存
            res.add(new ArrayList<Integer>(path));
            return;
        }
        for(int i=0;i<num.length;i++){
            // 若是已经存储该数字（下标），或者重复的数字中前一个数字没有访问过（说明是以后面为开始访问到前面的数是重复情况）
            if(set.contains(i) || (i>0 && num[i] == num[i-1] && !set.contains(i-1))){
                continue;
            }
            // 选择数字
            set.add(i);
            path.add(num[i]);
            dfs(num, set, path);
            // 撤销选择
            set.remove(i);
            path.remove(path.size()-1);
        }
    }

    public static void main(String[] args) {

    }
}
